package algorithmExample;

/**
 * @author: zhang.rongqing
 * @since: 2019/10/25
 */
//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
//        示例 1：
//
//        输入: "babad"
//        输出: "bab"
//        注意: "aba" 也是一个有效答案。
//        示例 2：
//
//        输入: "cbbd"
//        输出: "bb"
public class LongestPalindormic {
    public static String string;

    public String longestPalindrome(String s) {
        //最短的回文肯定是1，起始位第一个字符，最后一个也不用比较
        int offset = 1, end = s.length() - 1;
        if (s.length() == 0 || s == null) {
            return "";
        }
        String longestPalindorme = String.valueOf(s.charAt(0));
        for (int start = 0; start < end; start++) {
            String len1 = "", len2 = "";
            if (start - 1 >= 0 && s.charAt(start - 1) == s.charAt(start + 1)) {
                len1 = calcLongestStrOdd(s, start, offset, longestPalindorme);
            }
            if (s.charAt(start) == s.charAt(start + 1)) {
                len2 = calcLongestStrEven(s, start, offset, longestPalindorme);
            }
            String max = len1.length() > len2.length() ? len1 : len2;
            longestPalindorme = longestPalindorme.length() > max.length() ? longestPalindorme : max;
        }
        System.out.println(String.format("longestPalindorme:%s", longestPalindorme));
        return longestPalindorme;
    }

    public String calcLongestStrOdd(String str, int start, int offset, String longestPalindorme) {
        if (start - offset >= 0 && start + offset < str.length() && str.charAt(start + offset) == str.charAt(start - offset)) {
            //偏移量（两边的），加上中间的start为长度
            if (longestPalindorme.length() < offset * 2 + 1) {
                string = str.substring(start - offset, start + offset + 1);
            }
            calcLongestStrOdd(str, start, offset + 1, string);
        }
        return string;
    }

    public String calcLongestStrEven(String str, int start, int offset, String longestPalindorme) {
        if (start - offset + 1 >= 0 && start + offset < str.length() && str.charAt(start - offset + 1) == str.charAt(start + offset)) {
            //偏移量（两边的），加上中间的start为长度
            if (longestPalindorme.length() < offset * 2) {
                string = str.substring(start - offset + 1, start + offset + 1);
            }
            System.out.println(longestPalindorme);
            calcLongestStrEven(str, start, offset + 1, string);
        }
        return string;
    }

    public static void main(String[] args) {
        String str = "ccc";
//        String str = "abba";
        LongestPalindormic longestPalindormic = new LongestPalindormic();
        longestPalindormic.longestPalindrome(str);
    }
}
